package codeRandomThoughts.Test392判断子序列;

//动态规划
public class Solution2 {
    public boolean isSubsequence(String s, String t) {
        char[] charS = s.toCharArray();
        char[] charT = t.toCharArray();

        //dp[i][j]:下标范围0~i-1的字符串s和下标范围0~j-1的字符串t相同子序列的长度
        //此处要求t的长度是大于等于s的
        int[][] dp = new int[charS.length + 1][charT.length + 1];

        //初始化
        //因为我们dp数组定义的得当 所以初始化为0 可以直接省去

        //开始迭代
        for (int i = 1; i <= charS.length; i++) {
            for (int j = 1; j <= charT.length; j++) {
                if (charS[i - 1] == charT[j - 1]) {//这里要和dp数组对应
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    //不相等,说明charT[j-1]不起作用 直接排除掉
                    dp[i][j] = dp[i][j - 1];
                }
            }
        }

        return dp[charS.length][charT.length] == charS.length;
    }
}
